package demo8;

import java.util.*;
   class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
public class Solution {
    //1.有序数组中的单一元素(二分)
    public int singleNonDuplicate(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while(left < right) {
            int mid = (left + right) / 2;
            if(arr[mid] == arr[mid - 1]) {
                if((mid - left + 1) % 2 == 0) {
                    left = mid + 1;
                } else {
                    right = mid - 2;
                }
            } else if(arr[mid] == arr[mid + 1]) {
                if((right - mid + 1) % 2 == 0) {
                    right = mid - 1;
                } else {
                    left = mid + 2;
                }
            } else {
                return arr[mid];
            }
        }
        return arr[left];
    }

    //2.剑指 Offer II 074. 合并区间
    public int[][] merge(int[][] intervals) {
        //重写排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
               return o1[0] - o2[0];
            }
        });

        int high = intervals.length - 1;
        int[][] ret = new int[high][2];
        int index = -1;

        for(int[] interval : intervals) {
            //第一个一定放入
            if(index == -1 || ret[index][1] < interval[0]) {
                ret[++index] = interval;
            } else {
                //合并
                ret[index][1] = Math.max(ret[index][1], interval[1]);
            }
        }
        return Arrays.copyOf(ret, index + 1);
    }

    //3.剑指 Offer II 033. 变位词组
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, ArrayList<String>> map = new HashMap<>();
        for(int i = 0; i < strs.length; i++) {
            char[] chs = strs[i].toCharArray();
            Arrays.sort(chs);
            String s = String.valueOf(chs);
            if(!map.containsKey(s)) {
                map.put(s, new ArrayList<>());
            }
            map.get(s).add(strs[i]);
        }
        return new ArrayList<>(map.values());
    }

    //4.键值映射(map)
    class MapSum {

        private Map<String, Integer> map;

        public MapSum() {
            this.map = new HashMap<>();
        }

        public void insert(String key, int val) {
            map.put(key, val);
        }

        public int sum(String prefix) {
            int sum = 0;
            for(String key : map.keySet()) {
                if(key.startsWith(prefix)) {
                    sum += map.get(key);
                }
            }
            return sum;
        }

    }
    //5.剑指 Offer II 070. 排序数组中只出现一次的数字
//    public int singleNonDuplicate(int[] nums) {
//        int left = 0;
//        int right = nums.length - 1;
//        while(left < right) {
//            int mid = (left + right) / 2;
//            if(nums[mid] == nums[mid - 1]) {
//                if((mid - left + 1) % 2 == 0) {
//                    left = mid + 1;
//                } else {
//                    right = mid - 2;
//                }
//            } else if(nums[mid] == nums[mid + 1]) {
//                if((right - mid + 1) % 2 == 0) {
//                    right = mid - 1;
//                } else {
//                    left = mid + 2;
//                }
//            } else {
//                return nums[mid];
//            }
//        }
//        return nums[left];
//    }

    //6.最小时间差
    public int findMinDifference(List<String> timePoints) {
        //将时间全部用分钟表示
        List<Integer> timeList = new ArrayList<>();
        for(String time : timePoints) {
            String[] times = time.split(":");
            int sum = Integer.parseInt(times[0]) * 60 + Integer.parseInt(times[1]);
            timeList.add(sum);
            timeList.add(sum + 24 * 60);
        }
        Collections.sort(timeList);
        int min = Integer.MAX_VALUE;
        for(int i = 1; i < timeList.size(); i++) {
            int ans = Math.abs(timeList.get(i) - timeList.get(i - 1));
            if(ans < min) {
                min = ans;
            }
        }
        return min;
    }

    //7.前序遍历(迭代)
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList();
        if(root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            list.add(node.val);
            if(node.right != null) {
                stack.push(node.right);
            }
            if(node.left != null){
                stack.push(node.left);
            }
        }
        return list;
    }

    //8.
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            list.add(node.val);
            //这里和前序遍历调换顺序
            if(node.left != null) {
                stack.push(node.left);
            }
            if(node.right != null) {
                stack.push(node.right);
            }
        }
        Collections.reverse(list);
        return list;
    }

    //9.中序遍历(迭代法)
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()) {
            if(cur != null) {
                //让 cur 一路向左走,如果当前遍历元素不为空就入栈
                stack.push(cur);
                cur = cur.left;
            } else {
                //若当前元素为空，说明左边走到头了，这时候就可以弹出元素
                cur = stack.pop();
                list.add(cur.val);
                cur = cur.right;
            }
        }
        return list;
    }

//    //10.翻转二叉树
//    public void dfs(TreeNode root) {
//        if(root == null) {
//            return;
//        }
//        //交换左右指向
//        TreeNode tmp = root.left;
//        root.left = root.right;
//        root.right = tmp;
//        //左右两边也这样交换
//        dfs(root.left);
//        dfs(root.right);
//    }
//
//    public TreeNode invertTree(TreeNode root) {
//        dfs(root);
//        return root;
//    }

//    //翻转二叉树(方法二)
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }
        //优化
        if(root.left == null && root.right == null) {
            return root;
        }
        root.left = invertTree(root.left);
        root.right = invertTree(root.right);
        //交换左右结点
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        return root;
    }



}

class Main {

    public static void main(String[] args) {
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode7 = new TreeNode(7);
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode9 = new TreeNode(9);

        treeNode4.left = treeNode2;
        treeNode4.right = treeNode7;
        treeNode2.left = treeNode1;
        treeNode2.right = treeNode3;
        treeNode7.left = treeNode6;
        treeNode7.right = treeNode9;

        Solution solution = new Solution();
        solution.invertTree(treeNode4);
    }

}